#include<unordered_map>
using std::unordered_map;


struct DNode
{
    int key;
    int value;
    DNode *next;
    DNode *prev;
    DNode(int k, int v) : key(k), value(v), next(nullptr), prev(nullptr) {}
    DNode(): key(-1), value(-1), next(nullptr), prev(nullptr) {}
};



class LRUCache {
public:
    int capacity;
    DNode *head = new DNode(), *tail = new DNode();
    unordered_map<int, DNode*> mp;
    LRUCache(int capacity) {
        this->capacity = capacity;
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (mp.find(key) == mp.end()) return -1;
        auto node = mp[key];
        // 移到head
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (mp.find(key) != mp.end()) {
            // 已经有key
            mp[key]->value = value;
        }
        else {
            if (mp.size() == capacity) deleteLRU();
            mp[key] = new DNode(key, value);
        }
        moveToHead(mp[key]);
    }

    void deleteLRU() {
        auto node = tail->prev;
        if (node == head) return;
        auto x = node->prev;
        x->next = tail;
        tail->prev = x;
        mp.erase(node->key);
        delete node;
    }

    void moveToHead(DNode* x) {
        if (head->next == x) return;
        auto a = head->next;
        if (x->prev) x->prev->next = x->next;
        if (x->next) x->next->prev = x->prev;
        // insert to head
        head->next = x;
        x->next = a;
        a->prev = x;
        x->prev = head;
    }
};